import java.util.Arrays;

public class DP {
    public boolean canJump(int[] nums) {
        int len=nums.length;
        int max=1;
        for (int i=0;i<len;i++){
            if(max<i+1)break;
            max=Math.max(max,i+1+nums[i]);
        }
        return max>=len;
    }

    public int uniquePaths(int m, int n) {
        if(m==1||n==1)return 1;
        int mount=m+n-2;
        int time=1;
        for (int i=0;i<n-1;i++){
            time*=(mount-i);
        }
        for (int i=1;i<=n-1;i++){
            time=time/i;
        }
        return time;
    }

    public int coinChange(int[] coins, int amount) {
        long []count=new long[amount+1];
        for(int i=0;i<=amount;i++){
            count[i]=Integer.MAX_VALUE;
        }
        Arrays.sort(coins);
        int len=coins.length;
        count[0]=0;
        for(int i=len-1;i>=0;i--){
            int n=coins[i];
            for(int j=n;j<=amount;j++){
                count[j]=Math.min(count[j],count[j-n]+1);
            }
        }
        if(count[amount]==Integer.MAX_VALUE)return -1;
        else return (int)count[amount];
    }

    public int lengthOfLIS(int[] nums) {
        int len=nums.length;
        int []dp=new int[len];
        if(len<=0) return 0;
        int max=1;
        dp[0]=1;
        for(int i=1;i<len;i++){
            dp[i]=1;
            for(int j=0;j<i;j++){
                if(nums[i]>nums[j]){
                    dp[i]=dp[i]>(dp[j]+1)?dp[i]:(dp[j]+1);
                    max=max>dp[i]?max:dp[i];
                }
            }
        }
        return max;
    }
}
